package 每日一题;

public class No70爬楼梯 {

    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 注意：给定 n 是一个正整数。
     *
     * 示例 1：
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶
     * 2.  2 阶
     */

    private int[] arr;

    public int climbStairs(int n) {
        this.arr=new int[n+1];
        return dg(n);
    }

    private int dg(int k){
        if(k==0) {
            return 1;
        }
        if(k<=0) {
            return 0;
        }
        if(arr[k]!=0) {
            return arr[k];
        }
        int a=dg(k-1);
        int b=dg(k-2);
        arr[k]=a+b;
        return a+b;
    }

    public int climbStairsDbGood(int n) {

        /**
         * 自底向上
         */
        int[] db=new int[n+1];
        db[0]=0;
        db[1]=1;
        db[2]=2;
        for (int i = 3; i <= n ; i++) {
            //n-1阶爬1层就到n层||n-2阶爬2层就到n层= (n-1)+(n-2)
            db[i]=db[i-1]+db[i-2];
        }

        return db[n];
    }

    public static void main(String[] args) {
        No70爬楼梯 n=new No70爬楼梯();
        int i = n.climbStairs(25);
        System.out.println(i);
    }

}
